package org.example.BinaryTree;

public class Convert_ordered_arrays_to_binary_search_trees {
    public static void main(String[] args) {
        //将有序数组转换为二叉搜索树

        //给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
        //高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
        int[] nums = {1,3};
        TreeNode root = sortedArrayToBST(nums);
        search(root);
    }
    public static TreeNode sortedArrayToBST(int[] nums) {
        return getTree(nums, 0, nums.length - 1);
    }
    public static TreeNode getTree(int[] nums,int begin,int end){
        if (begin>end) return null;
        int index = (end-begin+1)/2+begin;
        TreeNode node = new TreeNode(nums[index]);
        node.left = getTree(nums,begin,index-1);
        node.right = getTree(nums,index+1,end);
        return node;
    }
    public static void search(TreeNode root){
        if (root==null) return;
        System.out.print(root.val+" ");
        System.out.print("进入左子树 ");
        search(root.left);
        System.out.print("进入右子树 ");
        search(root.right);
    }
}
